1. Field of the Invention
The present invention generally relates to a technique for two-dimensional image compression and, more particularly, to an image compression technique which represents a narrow class of images with very high efficiency. The invention has particular advantage in the transmission of specialized data through low bandwidth channels.
2. Background Description
Traditional strategies for two- and three-dimensional visualization have been effective in the development of interactive applications utilizing either workstation- or PC/game-class three-dimensional graphics systems with sufficient bandwidth for timely access to the data of interest. When remote access to the visualizations is required, the limited bandwidth becomes the primary bottleneck. To address this, data compression is considered as way of more effectively leveraging fixed and limited bandwidth for data transmission.
Data compression focuses largely on pattern manipulation. This is consistent with the entropy maximization principle of information theory. Clearly, by maximizing entropy, the number of patterns in a data stream are reduced, thereby removing redundancy and yielding a less bulky representation of the data. This operation entails the identification and re-representation of the pattern, the former being of particular difficulty. Hence, it is desirable to have the pattern identified a priori. For example, consider difference pulse code modulation (DPCM), in which the pattern of relative nearness of each succeeding value to its predecessor is exploited. By representing the data to remove the pattern, substantial reductions in required space may be made.
The human visual system is a source of the aforementioned pre-identified patterns for use in compression, some of which may be hierarchical. Therefore, levels of abstraction are introduced. The higher the level of abstraction, the more layers of human perceptual constructs are available to the compressor as starting points for pattern searching, and the closer the data are to their perceived meaning. In the present work, the image data are raster images depicting two-dimensional (2-D) projections of three-dimensional (3-D) scenes. Among the levels of abstraction for these data are bit-stream, pixel-map, 2-D geometry, and 3-D surfaces. Each implies different sets of redundancy when different sets of human perceptual constructs are used as starting points. For example, at the 2-D geometry level, a rectangular construct may be identified, and then re-represented as a directive for a rectangle followed by parameters.
At the least abstract (bit stream) level, virtually no human perceptual constructs are employed as a starting point for other patterns to be identified. Still, some patterns among the bits may be found, as seen by the performance of a generic compression algorithm (e.g., the LZW compression scheme).
At the pixel map level, some perceptual constructs are employed. These include the grid organization of the color values, the particular color space used, etc. In combination, simple patterns such as constant color areas of the image can be represented in a more compact way. The Joint Photographic Experts Group (JPEG) compression algorithm operates at this level by utilizing the reduced human perception of higher spatial frequencies of intensity values.
The 2-D geometry level of abstraction takes the context at the pixel map level and adds the perceptual constructs of geometry, such as lines, polygons, curves, etc. These patterns build on the basic constructs of color spaces, grids, etc. from the previous level. It is important to differentiate compression at this level from the common reverse-rasterization seen in the tracing applications available from companies like Corel and Adobe. The distinction is that the tracer uses a generic set of geometric patterns, while the compressor uses a set of geometric patterns most likely to be found in the images being compressed. Essentially, this is a custom metadata format, which will be very useful for compression of images having very similar types of geometric patterns. The 3-D surface level takes the geometric constructs identified at the previous level and matches the geometric patterns to projections of 3-D surfaces.